package com.fengdi.solutions.middle;

import com.fengdi.publicObject.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author FengDi
 * @Description  给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
 * @Solution 二叉搜索树的中序遍历序列是一个递增的有序序列，利用此特性遍历该树第K个遍历到的元素即为结果
 * */
public class _230_theK_MIniOfBinarySearchTree {
    private final List<Integer>list = new ArrayList<Integer>();

    public int kthSmallest(TreeNode root, int k) {
        this.dfs(root, k);
        System.out.println(this.list.toString());
        return this.list.get(k - 1);
    }

    public void dfs(TreeNode node, int k) {
        if(node == null) return;
        dfs(node.left, k); // 遍历左子树
        this.list.add(node.val);
        dfs(node.right, k); // 遍历右子树
    }
}
